//冒泡
function mySort(array) {
  let arr = array;

  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

//选择
function mySort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let index = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[index]) {
        index = j;
      }
    }
    [array[i], array[index]] = [array[index], array[i]];
  }
  return array;
}

//插入
function mySort(array) {
  for (let i = 1; i < array.length; i++) {
    for (let j = i; j > 0; j--) {
      if (array[j] < array[j - 1]) {
        [array[j], array[j - 1]] = [array[j - 1], array[j]];
      } else {
        break;
      }
    }
  }
  return array;
}

//快速排序

//移动元素 返回中间元素的index
function quicksort(arr, low, high) {
  let pre = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pre) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pre) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pre;
  return low;
}

function mySort(array, low, high) {
  if (low < high) {
    let pre = quicksort(array, low, high);
    mySort(array, low, pre - 1);
    mySort(array, pre + 1, high);
  }
  return array;
}

/**
 * 堆排序
 */
function buildMaxHeap(arr, len) {
  // 建立大顶堆
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i, len);
  }
}

function heapify(arr, i, len) {
  // 堆调整
  let left = 2 * i + 1,
    right = 2 * i + 2;
  let largest = i;
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest != i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, largest, len);
  }
}

function heapSort(arr) {
  let len = arr.length
  buildMaxHeap(arr,len)
  for(let i=arr.length-1;i>=0;i--){
    [arr[0],arr[i]]=[arr[i],arr[0]]
    len--
    heapify(arr,0,len)
  }
  return arr
}

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
arr=heapSort(arr)
console.log(arr); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
